package com.platform.modules.alg.alglib.hdu4812;

public class Hdu4812 {
    public int inf = 0x3f3f3f3f;
    public int P = 1000003;
    private int maxn = 100005;
    long inv[] = new long[P + 5]; // inv存储逆元,
    int mp[] = new int[P + 5]; // mp将乘积映射到节点
    long val[] = new long[maxn]; // 节点的值
    long d[] = new long[maxn]; // 节点到树根的乘积
    long dep[] = new long[maxn]; // 乘积序列
    int cnt, n, k, top;
    int head[];
    int id[] = new int[maxn]; // id[] 为节点序列
    int root, S;
    int size[] = new int[maxn];
    int f[] = new int[maxn];
    boolean vis[];
    int ans1, ans2;
    edge edge[] = new edge[maxn * 2];
    public String output = "";

    public Hdu4812() {
        for (int i = 0; i < edge.length; i++) {
            edge[i] = new edge();
        }
    }

    public String cal(String input) {
        int u, v;
        get_inv(); // 求1..P-1 的逆元
        int count = 0;
        String[] line = input.split("\n");
        while (true) {
            if (count == line.length) {
                break;
            }
            String[] num = line[count++].split(" ");
            n = Integer.parseInt(num[0]);
            k = Integer.parseInt(num[1]);
            vis = new boolean[maxn];
            cnt = 0;
            ans1 = ans2 = inf;
            head = new int[maxn];
            String[] vals = line[count++].split(" ");
            for (int i = 1; i <= n; i++) {
                val[i] = Long.parseLong(vals[i - 1]);
            }

            for (int i = 1; i < n; i++) {
                String[] connect = line[count++].split(" ");
                u = Integer.parseInt(connect[0]);
                v = Integer.parseInt(connect[1]);
                add(u, v);
                add(v, u);
            }
            root = 0;
            S = n;
            f[0] = n + 1;
            getroot(1, 0);
            solve(root);
            if (ans1 == inf)
                output += "No solution\n";
            else
                output += ans1 + " " + ans2 + "\n";
        }
        return output;
    }

    void add(int u, int v) {
        edge[++cnt].to = v;
        edge[cnt].next = head[u];
        head[u] = cnt;
    }

    // 求 1..P-1 的逆元
    void get_inv() {
        inv[1] = 1;
        for (int i = 2; i < P; i++)
            inv[i] = ((-P / i) * inv[P % i] % P + P) % P;
    }

    // 获取重心
    void getroot(int u, int fa) {
        size[u] = 1;
        f[u] = 0; // 删除 u 后，最大子树的大小
        for (int i = head[u]; i > 0; i = edge[i].next) {
            int v = edge[i].to;
            if (v != fa && !vis[v]) {
                getroot(v, u);
                size[u] += size[v];
                f[u] = Math.max(f[u], size[v]);
            }
        }
        f[u] = Math.max(f[u], S - size[u]); // S为当前子树总结点数
        if (f[u] < f[root])
            root = u;
    }

    // 获取乘积
    void getdep(int u, int fa) {
        dep[++top] = d[u]; // 保存乘积序列
        id[top] = u; // 保存节点
        for (int i = head[u]; i > 0; i = edge[i].next) {
            int v = edge[i].to;
            if (v != fa && !vis[v]) {
                d[v] = (d[u] * val[v]) % P; // 乘积 MOD P
                getdep(v, u);
            }
        }
    }

    void query(long x, int id) { // 积，节点编号
        x = inv[(int) x] * val[root] * k % P; // 求另一顶点的积
        int y = mp[(int) x];//映射到编号
        if (y == 0) return;
        // 保证 id>y
        if (y > id) {
            int temp = y;
            y = id;
            id = temp;

        }
        // 更新答案为最小编号
        if (y < ans1 || (y == ans1 && id < ans2)) {
            ans1 = y;
            ans2 = id;
        }
    }

    // 获取答案
    void solve(int u) {
        vis[u] = true;
        mp[(int) val[u]] = u; // 值映射到编号
        for (int i = head[u]; i > 0; i = edge[i].next) {
            int v = edge[i].to;
            if (!vis[v]) {
                top = 0; // 先求以v为根的子树
                d[v] = val[v] * val[u] % P; // 当前节点值为初值
                getdep(v, u);
                for (int j = 1; j <= top; j++) // 查询完毕再把这些积映射，以便下一个子树查询
                    query(dep[j], id[j]); // 第一个子树查询时，只有树根有映射，由此保证不会在一棵子树内部查询，因为这些节点还没有映射
                for (int j = 1; j <= top; j++)
                    if (mp[(int) dep[j]] == 0 || mp[(int) dep[j]] > id[j]) // 0 或 id[j] 比原来的值映射小
                        mp[(int) dep[j]] = id[j];
            }
        }
        mp[(int) val[u]] = 0; // 刚才赋值的 mp[] 清零
        for (int i = head[u]; i > 0; i = edge[i].next) {
            int v = edge[i].to;
            if (!vis[v]) {
                top = 0;
                d[v] = (val[u] * val[v]) % P;
                getdep(v, u);
                for (int j = 1; j <= top; j++)
                    mp[(int) dep[j]] = 0;
            }
        }
        for (int i = head[u]; i > 0; i = edge[i].next) {
            int v = edge[i].to;
            if (!vis[v]) {
                root = 0;
                S = size[v];
                getroot(v, 0);
                solve(root);
            }
        }
    }
}

class edge {
    int to, next;
}
